Algebra and Combinatorics of Parity Games
Identifieur interne : 003D38 ( Main/Exploration ); précédent : 003D37; suivant : 003D39Algebra and Combinatorics of Parity Games
Auteurs : Walid Belkhir [France]Source :
Descripteurs français
- mix :
English descriptors
- mix :
Abstract
Parity games are the combinatorial description of the theory of binary infimums, and supremums, and of the least and greatest fixed points over complete lattices. Roughly speaking, the parity games formalism may be understood as a μ-calculus over complete lattices. Hierarchies and logical expressiveness are at the core of fixed-point theory. The first part of this the- sis is devoted to consider the variable hierarchy problem within the lattice μ-calculus. Earlier works on this problem within the propositional modal μ- calculus have derived a complexity measure, the so called entanglement. The latter is the combinatorial counterpart of the variable hierarchy. The second part of this thesis is devoted to consider the entanglement as a pure graph theoretic measure, independently of its origins in fixed-point theory. Further results will be proved in this direction, such that the recognization of graphs of bounded entanglement, the tree decomposition of these graphs, and the closure under minors.
Url:
Affiliations:
- France
- Franche-Comté
- Belfort, Besançon
- Université de Bourgogne Franche-Comté, Université de Franche-Comté, Université de technologie de Belfort-Montbéliard
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000B80
- to stream Hal, to step Curation: 000B80
- to stream Hal, to step Checkpoint: 003046
- to stream Main, to step Merge: 003E67
- to stream Main, to step Curation: 003D38
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Algebra and Combinatorics of Parity Games</title><title xml:lang="fr">Algebre et Combinatoire des Jeux de Parité</title><author><name sortKey="Belkhir, Walid" sort="Belkhir, Walid" uniqKey="Belkhir W" first="Walid" last="Belkhir">Walid Belkhir</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno><idno type="RNSR">200412232H</idno><orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName><orgName type="acronym">FEMTO-ST</orgName><desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine><country key="FR"></country></address><ref type="url">http://www.femto-st.fr</ref></desc><listRelation><relation active="#struct-242365" type="direct"></relation><relation active="#struct-300261" type="direct"></relation><relation active="#struct-300360" type="direct"></relation><relation name="UMR6174" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-242365" type="direct"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno><idno type="ISNI">0000 0001 2188 3779 </idno><orgName>Université de Franche-Comté</orgName><orgName type="acronym">UFC</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.univ-fcomte.fr</ref></desc></org></tutelle><tutelle active="#struct-300261" type="direct"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName><orgName type="acronym">UTBM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300360" type="direct"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName><orgName type="acronym">ENSMM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR6174" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city" wicri:auto="siege">Besançon</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de Franche-Comté</orgName><orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName><placeName><settlement type="city" wicri:auto="siege">Belfort</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de technologie de Belfort-Montbéliard</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:tel-01277878</idno><idno type="halId">tel-01277878</idno><idno type="halUri">https://hal.inria.fr/tel-01277878</idno><idno type="url">https://hal.inria.fr/tel-01277878</idno><date when="2008-12-05">2008-12-05</date><idno type="wicri:Area/Hal/Corpus">000B80</idno><idno type="wicri:Area/Hal/Curation">000B80</idno><idno type="wicri:Area/Hal/Checkpoint">003046</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003046</idno><idno type="wicri:Area/Main/Merge">003E67</idno><idno type="wicri:Area/Main/Curation">003D38</idno><idno type="wicri:Area/Main/Exploration">003D38</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Algebra and Combinatorics of Parity Games</title><title xml:lang="fr">Algebre et Combinatoire des Jeux de Parité</title><author><name sortKey="Belkhir, Walid" sort="Belkhir, Walid" uniqKey="Belkhir W" first="Walid" last="Belkhir">Walid Belkhir</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno><idno type="RNSR">200412232H</idno><orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName><orgName type="acronym">FEMTO-ST</orgName><desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine><country key="FR"></country></address><ref type="url">http://www.femto-st.fr</ref></desc><listRelation><relation active="#struct-242365" type="direct"></relation><relation active="#struct-300261" type="direct"></relation><relation active="#struct-300360" type="direct"></relation><relation name="UMR6174" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-242365" type="direct"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno><idno type="ISNI">0000 0001 2188 3779 </idno><orgName>Université de Franche-Comté</orgName><orgName type="acronym">UFC</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.univ-fcomte.fr</ref></desc></org></tutelle><tutelle active="#struct-300261" type="direct"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName><orgName type="acronym">UTBM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300360" type="direct"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName><orgName type="acronym">ENSMM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR6174" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city" wicri:auto="siege">Besançon</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de Franche-Comté</orgName><orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName><placeName><settlement type="city" wicri:auto="siege">Belfort</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de technologie de Belfort-Montbéliard</orgName></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Games semantics</term><term>Graphs</term><term>Logic</term></keywords><keywords scheme="mix" xml:lang="fr"><term>Graphes</term><term>Logique</term><term>Sémantique</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Parity games are the combinatorial description of the theory of binary infimums, and supremums, and of the least and greatest fixed points over complete lattices. Roughly speaking, the parity games formalism may be understood as a μ-calculus over complete lattices. Hierarchies and logical expressiveness are at the core of fixed-point theory. The first part of this the- sis is devoted to consider the variable hierarchy problem within the lattice μ-calculus. Earlier works on this problem within the propositional modal μ- calculus have derived a complexity measure, the so called entanglement. The latter is the combinatorial counterpart of the variable hierarchy. The second part of this thesis is devoted to consider the entanglement as a pure graph theoretic measure, independently of its origins in fixed-point theory. Further results will be proved in this direction, such that the recognization of graphs of bounded entanglement, the tree decomposition of these graphs, and the closure under minors.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Franche-Comté</li></region><settlement><li>Belfort</li><li>Besançon</li></settlement><orgName><li>Université de Bourgogne Franche-Comté</li><li>Université de Franche-Comté</li><li>Université de technologie de Belfort-Montbéliard</li></orgName></list><tree><country name="France"><region name="Franche-Comté"><name sortKey="Belkhir, Walid" sort="Belkhir, Walid" uniqKey="Belkhir W" first="Walid" last="Belkhir">Walid Belkhir</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003D38 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003D38 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:tel-01277878
|texte= Algebra and Combinatorics of Parity Games
}}
| This area was generated with Dilib version V0.6.33. |  |